package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-08-28
 * 插入区间
 * \
 * 示例 1：
 *\
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 * 示例 2：
 *\
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 */
public class Insert {

    /**
     * 插入
     *
     * @param intervals   时间间隔
     * @param newInterval 新时间间隔
     * @return {@link int[][]}
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0], right = newInterval[1];
        List<int[]> ans = new ArrayList<>();
        //增加一个标记用来判断是否将新区间插入
        boolean place = false;
        for (int[] interval : intervals) {
            if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ans.add(interval);
            } else if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!place) {
                    ans.add(new int[]{left, right});
                    place = true;
                }
                ans.add(interval);
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        //防止区间刚好在最后一位时
        if (!place) {
            ans.add(new int[]{left, right});
        }
        return ans.toArray(new int[ans.size()][]);
    }

    public static void main(String[] args) {
        Insert insert = new Insert();
        int[][] intervals = new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] newInterval = new int[]{2,5};
        System.out.println(Arrays.deepToString(insert.insert(intervals, newInterval)));
    }

}
